#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include"queue_list.h"

#define TYPE char
#define MAX_VERTER 50

typedef struct Graph
{
	TYPE* verter;
	size_t size;
	int edge[MAX_VERTER][MAX_VERTER];
}Graph;


Graph* creat_graph(size_t size);
bool add_verter(Graph* gra,size_t i,TYPE ver);
bool add_edge(Graph* gra,int begin,int end);
void show_edge(Graph* gra);
void dfs_ergodic(Graph* gra);
void _dfs_ergodic(Graph* gra,int i,bool* flag);
void bfs_ergodic(Graph* gra);



//================================================================
int main()
{
	Graph* gra=creat_graph(5);
	for(int i=0;i<5;i++)
	{
		add_verter(gra,i,'A'+i);
	}
		add_edge(gra,0,1);
		add_edge(gra,0,2);
		add_edge(gra,0,3);
		add_edge(gra,3,2);
		add_edge(gra,1,3);
	show_edge(gra);
 	printf("\n-------------------\n");
	bfs_ergodic(gra);

}
//============================================
//创建图
Graph* creat_graph(size_t size)
{
	Graph* gra = malloc(sizeof(Graph));
	gra->verter = malloc(sizeof(TYPE)* size);
	gra->size = size;
	for(int i=0;i<size;i++)
	{
		gra->verter[i] = 0;
		for(int j = 0;j<size;j++)
		{
			gra->edge[i][j] = 0;	
		}
	}
	return gra;
	// memset(gra->edge,0,sizeof(int)*MAX_VERTER*MAX_VERTER);
}



//添加
bool add_verter(Graph* gra,size_t i,TYPE ver)
{
	if(i>=gra->size) return false;
	return gra->verter[i] = ver;
}
bool add_edge(Graph* gra,int begin,int end)
{
	if(begin< 0||begin>=gra->size||end<0||end>=gra->size ||begin == end||gra->edge[begin][end])
		return false;
	return gra->edge[begin][end]=1;
}




void show_edge(Graph* gra)
{	
	printf("  ");
	for(int i=0;i<gra->size;i++)
	{
		printf("%c ",gra->verter[i]);
	}
	printf("\n");
	for(int i=0;i<gra->size;i++)
	{
		printf("%c ",gra->verter[i]);
		for(int j=0;j<gra->size;j++)
		{
			printf("%d ",gra->edge[i][j]);	
		}
		printf("\n");
	}
}



//========================深度优先遍历================================
void _dfs_ergodic(Graph* gra,int i,bool* flag)
{


	if(flag[i])return;
	printf("%c ",gra->verter[i]);
	flag[i] =true;
	
	for(int j=0;j<gra->size;j++)
	{
		if(gra->edge[i][j])
			_dfs_ergodic(gra,j,flag);
	}
}
void dfs_ergodic(Graph* gra)
{
	bool flag[gra->size];
	for(int i=0;i<gra->size;i++)
	{
		flag[i]=0;	
	}
	for(int i=0;i<gra->size;i++)
	{	
		_dfs_ergodic(gra,i,flag);	
	}
	printf("\n");

}
//=======================广度优先遍历==============================
void bfs_ergodic(Graph* gra)
{
	Queue* queue = creat_queue();
	bool flag[gra->size];
	for(int i=0;i<gra->size;i++)
		flag[i]=false;
	for(int j=0;j<gra->size;j++)
	{
		if(gra->verter[j])
		push_queue(queue,j);
		
		while(!empty_queue(queue))
		{
			int k =*head_queue(queue);
			if(!flag[k])
			{
				printf("%c ",gra->verter[k]);
				flag[k]=true;
			}
			for(int l=0;l<gra->size;l++)
			{
				if(gra->edge[k][l])
				{
					push_queue(queue,l);
				}
			}
			pop_queue(queue);
		}
	}
	
}

/*
void _bfs_ergodic(Graph* gra,int i,bool* flag,Queue* queue)
{
	if(flag[i]) return;
	push_queue(queue,i);

	for(int j=0;j<gra->size;j++)
	{
		if(gra->edge[i][j])
			push_queue(queue,j);
		while(!empty_queue)
		{
			int k=*head_queue(queue);	
			if(!flag[k])
			{
				printf("%c ",gra->verter[k]);
				flag[k] = true;
			}
			for(int l=0;l<gra->size;l++)
			{
				if(gra->edge[k][l])
				push_queue(queue,l);
			}
			pop_queue(queue);
		}
	}
}
void bfs_ergodic(Graph* gra)
{
	Queue* queue=creat_queue();
	bool flag[gra->size];
	for(int i=0;i<gra->size;i++)
	{
		flag[i]=0;		
	}
	for(int i=0;i<gra->size;i++)
	{	
		_bfs_ergodic(gra,i,flag);	
	}
	destory_queue(queue);
	printf("\n");
}
*/














